Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs

摘要

We extract a novel quantum programming paradigm - superposition of programs -from the design idea of a popular class of quantum algorithms, namely quantumwalk-based algorithms. The generality of this paradigm is guaranteed by theuniversality of quantum walks as a computational model. A new quantumprogramming language QGCL is then proposed to support the paradigm ofsuperposition of programs. This language can be seen as a quantum extension ofDijkstra's GCL (Guarded Command Language). Surprisingly, alternation in GCLsplits into two different notions in the quantum setting: classical alternation(of quantum programs) and quantum alternation, with the latter being introducedin QGCL for the first time. Quantum alternation is the key program constructfor realizing the paradigm of superposition of programs. The denotational semantics of QGCL are defined by introducing a newmathematical tool called the guarded composition of operator-valued functions.Then the weakest precondition semantics of QGCL can straightforwardly derived.Another very useful program construct in realizing the quantum programmingparadigm of superposition of programs, called quantum choice, can be easilydefined in terms of quantum alternation. The relation between quantum choicesand probabilistic choices is clarified through defining the notion of localvariables. We derive a family of algebraic laws for QGCL programs that can beused in program verification, transformations and compilation. The expressivepower of QGCL is illustrated by several examples where various variants andgeneralizations of quantum walks are conveniently expressed using quantumalternation and quantum choice. We believe that quantum programming withquantum alternation and choice will play an important role in furtherexploiting the power of quantum computing.